//不同路径||| (hard) : https://leetcode.cn/problems/unique-paths-iii/
class Solution {
public:
    int path;
    int ret;
    int n,m;
    int ZeroSum;
    bool vis[25][25];  //只判断0
    int uniquePathsIII(vector<vector<int>>& grid) {
        n=grid.size(),m=grid[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==0)
                {
                    ZeroSum++;
                }
            }
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==1)
                {
                    dfs(grid,i,j);
                }
            }
        }
        return ret;
    }
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    void dfs(vector<vector<int>>& grid,int i,int j)
    {
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];     int y=j+dy[k];
            if(x>=0&&x<n&&y>=0&&y<m && (grid[x][y]==0||grid[x][y]==2) )
            {
                if(grid[x][y]==2 && ZeroSum==path)    //走2，只有2可走 ---注意：还要已经被访问过的0可以走
                {
                    ret++;
                    return;
                }
                //其他情况，走0
                if(vis[x][y]==0 && grid[x][y]==0)
                {
                    vis[x][y]=1;  path++;
                    dfs(grid,x,y);
                    vis[x][y]=0;  path--;
                }
            }
        }
    }
};

//图像渲染(easy) : https://leetcode.cn/problems/flood-fill/description/
class Solution {
public:
    int OldColor;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m,n;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image[sr][sc]==color)   return image;
        m=image.size(),n=image[0].size();
        OldColor=image[sr][sc];
        image[sr][sc]=color;
        dfs(image,sr,sc,color);
        return image;
    }
    void dfs(vector<vector<int>>& image,int i,int j,int color)
    {
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];     int y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&& image[x][y]==OldColor)
            {
                image[x][y]=color;
                dfs(image,x,y,color);
            }
        }
    }
};